package 栈;

/* https://leetcode-cn.com/problems/valid-parentheses/ */

import java.util.Stack;

public class _20_有效的括号 {
    public boolean isValid(String s) {

        // 解题核心：通过栈这个数据结构的特殊性解决
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0;i<len;i++){
            char c = s.charAt(i);
            if (c == '[' || c == '(' || c == '{'){
                stack.push(c);
            }else {
                // 如果栈里面为空，说明没有左边的符号，这时候直接返回false
                if (stack.isEmpty())return false;
                // left_char与右边的符号开始对应，如果符号不匹配，直接返回false
                char left_char = stack.pop();
                if (left_char == '[' && c != ']'){return false;}
                if (left_char == '(' && c != ')'){return false;}
                if (left_char == '{' && c != '}'){return false;}

            }
        }
        /* 如果能走到这里，说明全部匹配完了，这时候如果栈里面还有值，说明有一个没匹配到，则这时返回false，为空说明
        全部配得上而且匹配完了,返回true */
        return stack.isEmpty();
    }
}
